index.md (1307B)
1 +++ 2 title = 'Hamilton: vertices matter' 3 +++ 4 # Hamilton: vertices matter 5 a Hamilton cycle contains every vertex exactly once 6 7 G is Hamiltonian if it has a Hamilton cycle (but it’s hard to prove that it is, no efficient algorithm) 8 9 to show that G is not Hamiltonian: 10 11 - if G is Hamiltonian, then for any nonempty V* ⊆ V(G) 12 - the graph G-V* contains at most |V*| components 13 - w(G-V*) ≤ |V*| 14 - if not true, graph not Hamiltonian 15 16 Dirac’s criterion 17 18 - if G has n ≥ 3 vertices and ∀v: δ(v) ≥ n/2 19 - then G is Hamiltonian 20 21 Finding Hamilton cycles using Posa rotational transformations 22 23 - Pick starting vertex u. Initial path P=[u] 24 - while P is not a Hamilton cycle: 25 - If possible, select y from N(last added vertex) excluding vertices already in path 26 - then add that y to the path 27 - else, pick a v from N(last added vertex). Because v is already in path, there is an edge from *v* to some other vertex *x*. 28 - do a switcherino — connect v to w, and reverse path from w to x: 29 30  31 32 Traveling salesman problem: 33 34 - finding a shortest Hamilton cycle in a complete, weighted graph 35 - because of Hamilton, there’s no efficient algorithm for this 36 - greedy algorithm: start with arbitrary cycle, swap edges if it reduces overall weight